Optimal sorting algorithm with modified cost... [closed]
Posted
by
David
on Stack Overflow
See other posts from Stack Overflow
or by David
Published on 2011-01-14T03:13:19Z
Indexed on
2011/01/14
21:53 UTC
Read the original article
Hit count: 270
The numbers are in a list that is not sorted and supports only one type of operation. The operation is defined as follows: Given a position i and a position j the operation moves the number at position i to position j without altering the relative order of the other numbers. If i > j, the positions of the numbers between positions j and i - 1 increment by 1, otherwise if i < j the positions of the numbers between positions i+1 and j decreases by 1. This operation requires i steps to find a number to move and j steps to locate the position to which you want to move it. Then the number of steps required to move a number of position i to position j is i+j. Design an algorithm that given a list of numbers, determine the optimal(in terms of cost) sequence of moves to rearrange the sequence.
© Stack Overflow or respective owner